package com.zjsru.plan2024.oneday;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Author: cookLee
 * @Date: 2024-01-30
 * 使循环数组所有元素相等的最少秒数：将 nums[i] 替换成 nums[i] ，nums[(i - 1 + n) % n] 或者 nums[(i + 1) % n] 三者之一。
 */
public class MinimumSeconds {

    /**
     * 主
     * \
     * 输入：nums = [1,2,1,2]
     * 输出：1
     * 解释：我们可以在 1 秒内将数组变成相等元素：
     * - 第 1 秒，将每个位置的元素分别变为 [nums[3],nums[1],nums[3],nums[3]] 。变化后，nums = [2,2,2,2] 。
     * 1 秒是将数组变成相等元素所需要的最少秒数。
     * \
     * 输入：nums = [2,1,3,3,2]
     * 输出：2
     * 解释：我们可以在 2 秒内将数组变成相等元素：
     * - 第 1 秒，将每个位置的元素分别变为 [nums[0],nums[2],nums[2],nums[2],nums[3]] 。变化后，nums = [2,3,3,3,3] 。
     * - 第 2 秒，将每个位置的元素分别变为 [nums[1],nums[1],nums[2],nums[3],nums[4]] 。变化后，nums = [3,3,3,3,3] 。
     * 2 秒是将数组变成相等元素所需要的最少秒数。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        MinimumSeconds minimumSeconds = new MinimumSeconds();
        List<Integer> nums = new ArrayList<>();
        nums.add(1);
        nums.add(2);
        nums.add(3);
        nums.add(4);
        nums.add(5);
        System.out.println(minimumSeconds.minimumSeconds(nums));
    }

    /**
     * 最小秒数:哈希表
     *
     * @param nums nums
     * @return int
     */
    public int minimumSeconds(List<Integer> nums) {
        int ans = nums.size();
        Map<Integer, List<Integer>> map = new HashMap<>();
        //记录相同的数在数组中出现的位置
        for (int i = 0; i < nums.size(); i++) {
            map.computeIfAbsent(nums.get(i), k -> new ArrayList<>()).add(i);
        }
        for (List<Integer> positions : map.values()) {
            //获取头尾之间的距离的最大值，类似将数字看作环状来获取间隔的最大值
            int mx = positions.get(0) + nums.size() - positions.get(positions.size() - 1);
            for (int i = 1; i < positions.size(); i++) {
                //因为扩散规则限制，替换时选中当前数字nums[i]来更换，那么更换的时间应该是相邻数字的最大值
                mx = Math.max(mx, positions.get(i) - positions.get(i - 1));
            }
            //因为更换是相同数字同时进行，那么相邻之间的数字是mx/2
            ans = Math.min(ans, mx / 2);
        }
        return ans;
    }

}
